home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / cc02.arc / CSORT2.C < prev    next >
Text File  |  1986-03-14  |  2KB  |  103 lines
  1. /* -- csort.c  sorting benchmark -- */
  2. /* ---- calls random the number of times specified by MAX to create an
  3.     array of lon integers, then does a quicksort on the array of longs.
  4.     The program does this for the number of times specified by NTIMES.
  5.    ---- */
  6.  
  7. #include "stdio.h"
  8.  
  9. #define MAX 1001            /* maximum number of entries */
  10. #define MAXLINE 135            /* longest line expected */
  11. #define NTIMES 10            /* number of times to sort entries */
  12.  
  13. main() {                /*sort lines in memory */
  14.     int i,j, n, length;
  15.     char buf[MAXLINE], *sort[MAX], *unsorted[MAX], *alloc();
  16.  
  17.     for (n = 0; n < MAX; n++)
  18.         if ((length = getln(buf, MAXLINE)) == 0) {
  19.             n--;
  20.             break;
  21.         }
  22.         else if ((unsorted[n] = alloc(length + 1)) == NULL) {
  23.             printf("Sort: not enough room\n");
  24.             exit(-1);
  25.         }
  26.         else    strcpy(unsorted[n], buf);
  27.  
  28.     printf("%d iterations: ", NTIMES);
  29.  
  30.     for (i = 1; i <= NTIMES; i++) {
  31.         for (j = 0; j <= n; j++)
  32.             sort[j] = unsorted[j];
  33.         quick(0, n, sort);
  34.     }
  35.  
  36.     printf("%d entries.\n", n + 1);
  37.     exit(0);
  38. }
  39.  
  40. quick(lo, hi, base)            /* quicksort */
  41.  
  42.     int lo, hi;
  43.     char *base[];
  44.  
  45.     {
  46.         int i, j;
  47.         char *pivot, *temp;
  48.  
  49.         if (lo < hi) {
  50.             for (i = lo, j = hi, pivot = base[hi]; i < j; ) {
  51.                 while (i < j && strcmp(base[i], pivot) <= 0)
  52.                     i++;
  53.                 while (j > i && strcmp(base[j], pivot) >= 0)
  54.                     j--;
  55.                 if (i < j) {
  56.                     temp = base[i];
  57.                     base[i] = base[j];
  58.                     base[j] = temp;
  59.                 }
  60.             }
  61.             temp = base[i];
  62.             base[i] = base[hi];
  63.             base[hi] = temp;
  64.             quick (lo, i - 1, base);
  65.             quick (i + 1, hi, base);
  66.         }
  67.     }
  68.  
  69. getln(s, n)                /* get a line of up to n characters into s */
  70.  
  71.     char s[];
  72.     int n;
  73.  
  74.     {
  75.         int c, i;
  76.  
  77.         for (i = 0; n > 0; n--, i++)
  78.             if ((c = getchar()) == EOF || c == '\n')
  79.                 break;
  80.             else    s[i] = c;
  81.         s[i] ='\0';
  82.         return(i);
  83.     }
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.